带权无向图的邻接矩阵表示法(C语言实现) |
您所在的位置：网站首页 › 有向图 邻接矩阵 › 带权无向图的邻接矩阵表示法(C语言实现) |
带权无向图的邻接矩阵表示法(C语言实现)
|
带权无向图的邻接矩阵表示法(C语言实现)
文章目录
带权无向图的邻接矩阵表示法(C语言实现)一、邻接矩阵表示法二、本次程序实现的功能三、带权无向图的结构体定义四、创建无向图及邻接矩阵五、输出邻接矩阵六、输出顶点集合七、判断两顶点是否邻接八、全部代码九、测试
一、邻接矩阵表示法
定义：所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。 对于带权图而言，若顶点Vi 和 Vj 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点Vi 和 Vj 不相连，则用0或∞来代表这两个顶点之间不存在边。 例如，对于下面这样一个图：
我们可以得到其邻接矩阵： 注：括号内的0、1、2、3代表其二维数组的下标。 容易发现，带权邻接矩阵有以下特点：①关于主对角线元素对称；②非0的对应位置上的值即为边的权值。 如果是不带权，那么有边的对应位置为1，没边的位置为0，同样也是关于主对角线元素对称。 二、本次程序实现的功能创建无向图的邻接矩阵 输出无向图对应的邻接矩阵 输出顶点集合 判断两顶点是否邻接，即是否存在直接相连的边 三、带权无向图的结构体定义 typedef char VertexType; //顶点的数据类型 typedef int EdgeType; //带权图中边上权值的数据类型 typedef struct { VertexType Vex[MaxVertexNum]; //顶点表 MaxVertexNum是最大的顶点数目,下同 EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表 int vexnum, arcnum; //图的当前顶点数和边数 }MGraph;//基于邻接矩阵法的带权无向图 四、创建无向图及邻接矩阵 由于比较简单，就不多解释了。值得注意的是，要好好利用无向图的邻接矩阵关于主对角线对称的特性，所以输入边权值时只需要输入上三角或下三角。 void CreateMGraph(MGraph *G) { int i,j,k,w; //先确定顶点数和边数 printf("请输入顶点数和边数,用空格隔开:\n"); scanf("%d %d",&G->vexnum,&G->arcnum); fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入 //依次输入顶点的值 printf("请依次输入顶点的值:\n"); for(int i = 0;i vexnum; i++) { printf("输入第%d个顶点信息:\n",i+1); scanf("%c",&G->Vex[i]); //接收值放入顶点表中 fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入 } //初始化邻接矩阵 for(i = 0;i vexnum; i++) for(j = 0;j vexnum; j++) G->Edge[i][j] = 0;//开始时全部初始化为0,也可以用∞ //建立邻接矩阵 for (k = 0; k arcnum; k++) { printf("输入边的下标i,下标j和权w:\n"); scanf("%d%d%d", &i, &j, &w); //输入边上的权值w G->Edge[i][j] = w; G->Edge[j][i] = G->Edge[i][j]; //无向图矩阵是对称的 } } 五、输出邻接矩阵 本质就是遍历一个二维数组。 //输出邻接矩阵 void PrintMatrix(MGraph G) { int i,j; printf("邻接矩阵表示如下:\n"); for (i = 0; i Vex[i]); //接收值放入顶点表中 fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入 } //初始化邻接矩阵 for(i = 0;i vexnum; i++) for(j = 0;j vexnum; j++) G->Edge[i][j] = 0;//开始时全部初始化为0,也可以用∞ //建立邻接矩阵 for (k = 0; k arcnum; k++) { printf("输入边的下标i,下标j和权w:\n"); scanf("%d%d%d", &i, &j, &w); //输入边上的权值w G->Edge[i][j] = w; G->Edge[j][i] = G->Edge[i][j]; //无向图矩阵是对称的 } } //输出邻接矩阵 void PrintMatrix(MGraph G) { int i,j; printf("邻接矩阵表示如下:\n"); for (i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |